This invention is concerned with the decoding of the information bearing sequences, which occur in modem digital communication systems. In particular, the present invention is concerned with a system and method for decoding information bearing sequences received from an intersymbol-interference communication channel, from a noisy communication channel, or from recording devices.
In modern communication and recording systems, information symbols in neighboring data tracks on a disc or adjacent bits in a transmission sequence sometimes interfere with each other during the transmission through the channel. In this case, the term “channel” refers to the medium from which the information symbols are received. This interference is known as “intersymbol interference” (ISI), and ISI impairs the performance of a communication system.
While the elimination of ISI would be optimal, in many systems, ISI cannot be completely eliminated. However, steps can be taken to reduce the effect of ISI on the error rate of information transmissions.
One way of reducing the effect of ISI is to equalize the channel's impulse response to a pre-defined transfer function. The pre-defined transfer function does not eliminate ISI. Instead, using the known intersymbol interference, the receiver can reduce the effect of ISI by using a proper decoding algorithm. This method of communication is referred to as partial-response (PR) signaling. A general description of PR signaling is given by P. Kabel et al., in the paper “Partial Response Signaling,” IEE Transaction on communications, Vol. COM-23, No. 9, September 1975, pp 921-934. Generally, partial-response signaling allows for better handling of the intersymbol interference and for more efficient utilization of the bandwidth of a given channel.
Maximum-likelihood sequence detection (MLSD), in particular the Viterbi algorithm (VA), is a method for the detection of the sequences in the presence of intersymbol interference. A general description of this technique was provided by G. D. Forney in “The Viterbi Algorithm,” published in the proceedings of the IEEE, Vol. 61, No. 3, March 1973, pp. 268-278, and by G. Ungerboeck, “Adaptive Maximum-likelihood Receiver for Carrier-modulated Data Transmission Systems,” in the IEEE Transactions on Communications, Vol. COM-22, No. 5, May 1974, pp. 624-636. The Viterbi Algorithm currently is used in many communication and recording systems.
The Soft-Output Viterbi Algorithm (SOVA) is a modification of the VA that gives the most likely path sequence in the trellis, as well as the a posteriori probability for each transmitted bit. A general description of the SOVA technique was described by J. Hagenauer and P. Hoeher in the article “A Viterbi algorithm with soft decision outputs and its applications,” in the Proc. GLOBECOM'89, pp. 1680-1686. Optimal a posteriori probabilities are also given by the so-called BCJR algorithm. A general description of the BCJR algorithm was provided in the article authored by L. Bahl, J. Cocke, F. Jelinek, and J. Raviv, entitled “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans.on Information Theory, pp. 284-287, March 1974. Both the Viterbi and the BCJR algorithms, when combined with a soft decoding scheme for convolution modulation codes, form efficient iterative “turbo” decoding schemes. Both the SOVA and the BCJR algorithm can be used in the partial response (PR) channels.
Although the bit-error rate (BER) of the turbo algorithm approach Shannon's theoretical limit, the complexity of their implementation and the time delays introduced by these algorithms through the decoding process pose serious problems for real-time information retrieval.
One potential solution to this problem involves low-density parity-check (LDPC) codes. LDPC codes have orthogonal parity checks on all message bits, which allows a message bit to be determined by majority voting at a single decoding step. LDPC codes belong to a class of codes referred to as “one step majority decodable codes”, which are discussed in a book authored by S. Lin and D. J. Costello. Jr. entitled “Error control coding: fundamentals and applications”, and published by Prentice Hall in 1983.
Generally, one step majority decodable codes support message-passing decoding, an iterative decoding algorithm on a code graph. “Messages” are descriptions of local function products (possibly marginalized local function products). The functions are “local” in the sense that access to the functions is local to a specific vertex in the graph. Knowledge of local functions (or functions derived from local functions such as probabilities) can be propagated to non-local vertices by “message passing” along the edge of the graph. Essentially, messages are passed between the vertices of the “propagation tree”.
While one step majority decodable codes work for some applications, it is known that it is not possible to construct short and powerful LDPC codes that, at the same time, have a high code rate. The high rate LDPC codes capable of correcting burst and ISI errors are long. However, long codes result in coding delays, which may not be tolerable in practical applications. In particular, coding delays in magnetic recording would be intolerable. The code rate is very important in magnetic recording because low code rates amplify the signal-to-noise ratio (SNR) loss. The issues related to the code rate loss in baseband communication and recording channels are well known.
Therefore, it is desirable to have a coding system that offers high coding rates with shorter codes; and it is desirable to have a Turbo decoder capable of decoding the shorter codes at a high code rate.